The present invention relates to programmable logic device, and more particularly to coverage of programmable interconnect points in a programmable logic device.
Programmable logic devices (PLDS) exist as a well-known type of integrated circuit (IC) that may be programmed by a user to perform specified logic functions. There are different types of programmable logic devices, such as programmable logic arrays (PLAs) and complex programmable logic devices (CPLDs). One type of programmable logic devices, called the field programmable gate array (FPGA), is very popular because of a superior combination of capacity, flexibility and cost.
A typical FPGA comprises a large number of configurable logic blocks (CLBs) surrounded by input-output blocks and interconnectable through a routing structure. The routing structure comprises many interconnect wires and associated programmable interconnect points (PIPs). In one embodiment, a PIP contains a pass transistor that can be turned on and off, thereby allowing an associated interconnect wire to be either connected or disconnected (depending on the state of the transistor) to other circuit elements. The CLBs and routing structure of the FPGA are arranged in an array or in a plurality of sub-arrays wherein respective CLBs and associated portions of the routing structure are placed edge to edge in what is commonly referred to as a tiled arrangement. The CLB portion of a tile comprises a plurality of primitive cells which may be interconnected in a variety of ways to perform a desired logic function. For example, a CLB may comprise a plurality of lookup tables (LUTS), multiplexers and registers. The CLBs, IOBs, and interconnect structure are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the CLBS, IOBs, and interconnect structure are configured. The configuration bitstream may be read from an external memory (e.g., an external PROM). The collective states of the individual memory cells then determine the function of the FPGA.
It can be seen from above that a typical FPGA is a very complex IC device. For example, some FPGAs in the Virtex-II family, marketed by Xilinx, Inc. of San Jose, Calif., contain several million gates. In addition, there are millions of interconnect lines. A FPGA may be unusable when a very small number of gates, PIPs or interconnect lines malfunction (e.g., due to fabrication errors, fabrication defects, or physical failure). Thus, it is important to test the FPGA to determine if there are defects.
One criteria of a successful testing is whether at least a predetermined percentage of PIPs have been tested. If not enough PIPs have been tested, the chance that a user design may use one of the untested PIPs (which may be faulty) is unacceptably high. Consequently, there is a need to be able to test as many PIPs as possible efficiently.
The present invention involves methods for increasing the number of PIPs that can be covered in a routing. A file is set to store information indicating whether a PIP has been covered. A predetermined value (used for modifying the cost) is inputted. The node are then routed. The routing routine includes expanding from a first node to a second node. A modified cost for the second node (equal to cost of the first node plus base cost of the second node minus the inputted value) is calculated. This modified cost is applied if the first node and a second node are connected through an uncovered PIP and if the modified cost is lower than the cost of the second node. Routing is performed using the cost calculated above.
In another embodiment of the present invention, a signal from a routed pattern is ripping up. Routing is performed on the ripped up signal by applied the above method. Other signals in the routed pattern can also be ripped up and rerouted.
In yet another embodiment of the present invention, a different file is set up. This file stores a xe2x80x9ccountxe2x80x9d for each PIP. The nodes are then routed. A new cost is calculated by adding to the base cost a term equal to a product of the count and a predetermined value. After a routing run, the file is updated by increasing the count of each visited PIP by one.
The above summary of the present invention is not intended to describe each disclosed embodiment of the present invention. The figures and detailed description that follow provide additional example embodiments and aspects of the present invention.